#!/usr/bin/python
# encoding: utf-8
'''
Francisco do Ó nr5202
'''
'''
Lista ligada - estrutura de dados onde os objectos sao dispostos numa ordem linear.
A ordem na lista é determinada pelos apontadores de cada objecto, neste caso
para o objecto anterior e posterior
'''
class LinkedList:
        '''
        Inicialização da lista ligada que representará a pilha. 
        @param N tamanho da lista
        '''
	def __init__(self,N):
		self.apontadores_memoria = Stack(N)
		for k in range(N):
			self.apontadores_memoria.push(k)
		self.key =  [0 for k in range(N)]
                self.valor =  [0 for k in range(N)]
                self.prev = [0 for k in range(N)]
                self.next = [0 for k in range(N)]
		
                self.head = None
        '''
        Alocação da memória para um novo nó
        com a inicializaçao dos apontadores para o elemento anterior e posterior
        @param k: chave do nó
        @param v: valor do nó
        '''
	def malloc(self, k,v):
		x = self.apontadores_memoria.pop()
		self.key[x] = k
                self.valor[x] = v
		self.prev[x] = None
		self.next[x] = None
		return x
        '''
        Liberta elemento da memória
        @param x: apontador para o elemento
        '''
	def free(self, x):
		self.apontadores_memoria.push(x)

        '''
        insere novo elemento na lista 
        organiza apontadores
        @param x: apontador elemento
        '''
	def insert(self, x):
                self.next[x] = self.head
                if self.head != None:
                        self.prev[self.head] = x
                self.head = x
                self.prev[x] = None

        '''
        Procura de elemento dado um par chave,valor 
        @param k: chave do nó
        @param v: valor do nó
        '''
        def search(self, k,v):
                x = self.head
                while x != None and self.key[x] != k and self.valor[x] != v:
                        x = self.next[x]
                return x
        '''
        Apaga elemento da lista
        @param x : apontador para o elemento
        '''
        def delete(self,x):
                if self.prev[x] != None:
                        self.next[self.prev[x]] = self.next[x]
                else:
                        self.head = self.next[x]
                if self.next[x] != None:
			self.prev[self.next[x]] = self.prev[x]
        '''
        Imprime lista ligada da pilha com os elementos e devidos apontadores 
        @param N: tamanho da lista
        '''
        def printStack(self,N):
                print '\n****************** Representação da Memória (Stack) Numa Lista Ligada *******************'
                for k in range(N):
                        print "x:", k, self.head, "key: ", \
                        self.key[k], "value: \""+str(self.valor[k])+"\"", "next: ", self.next[k], \
                        "prev: ", self.prev[k],""

'''
A pilha representa um tipo de dados abstracto LIFO (Last In First Out), 
onde os últimos elementos a serem inseridos são os primeiros a serem resolvidos. 
'''      
class Stack:
        '''
        Inicialização da pilha (stack).
        @param N: tamanho da pilha  
        '''
        def __init__(self, N):
                self.top = -1
                self.stack = [0 for k in range(N)]
                pass
        
        '''verifica se a pilha está vazia ou não'''
        def stack_empty(self):
                if self.top == 0:
                        return True
                else:
                        return False
        ''' 
        inserção (push) de elemento na pilha.
        @param x: apontador elemento
        '''
        def push(self, x):
                self.top += 1
                self.stack[self.top] = x
                pass
                
        '''remoção (pop) elemento na pilha.'''
        def pop(self):
                if self.stack_empty():
                        return "underflow"
                else:
                        self.top -= 1
                        return self.stack[self.top+1]
                pass
        pass	